package SwordFingerOffer;

public class Q46_NumToString {

    //12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
    //青蛙跳台阶问题 小 dp

    public int translateNum(int num) {
        //数字转数组 ==>
        String str = String.valueOf(num);
        return process(str, 0);
    }

    //返回方案数
    public int process(String str, int index){
        //base case
        //有效方案
        if (index == str.length() - 1 || index == str.length()){
            return 1;
        }
        //无效方案
//        if (index > str.length()){
//            return 0;
//        }
        int count = 0;
        //当场翻译 去下一个
        if (str.charAt(index) > '2'){
            count += process(str, index + 1);
            //当前字符可拼接 <= 2 再看下一步是不是可拼接
            //连同下一个一起翻译 或者 当场翻译
        }else if ((str.charAt(index) == '2' && str.charAt(index + 1) <= '5')
                || (str.charAt(index) < '2' && str.charAt(index) > '0')
        ){
                count += process(str, index + 2) + process(str, index + 1);
        }else {
                //下一位不可拼接 当场翻译
                count += process(str, index + 1);
            }

        return count;
    }

    public static void main(String[] args) {
        Q46_NumToString fun = new Q46_NumToString();
        System.out.println(fun.translateNum(18580));
    }
}
